package com.maishi.programmer.jainzhioffer;

import java.util.ArrayList;
import java.util.TreeSet;

/**
 * Created by brossdong on 2018/4/5.
 * 输入n个整数，找出其中最小的K个数。
 * 例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
 */
public class TestProblem40 {

    /**
     * 考虑到不改变原来数组的顺序
     * 时间复杂度为O(nlogk)
     * @param input
     * @param k
     * @return
     */
    /**
     * 先找到容器中的最大值；
     * 将待查入值和最大值比较，如果待查入值大于容器中的最大值，则直接舍弃这个待查入值即可；
     * 如果待查入值小于容器中的最小值，则用这个待查入值替换掉容器中的最大值；
     * 重复上述步骤，容器中最后就是整个数组的最小k个数字。
     * 对于这个容器的实现，我们可以使用最大堆的数据结构，
     * 最大堆中，根节点的值大于它的子树中的任意节点值。
     * Java中的TreeSet类实现了红黑树的功能，它底层是通过TreeMap实现的，
     * TreeSet中的数据会按照插入数据自动升序排列（按自然顺序）。
     * 因此我们直接将数据依次放入到TreeSet中，数组就会自动排序。
     */
    public static ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {

        ArrayList<Integer> list = new ArrayList<Integer>(k);
        if (input == null) return null;
        if (k > input.length) return list;
        TreeSet<Integer> tree = new TreeSet<>();
        for (int i = 0;i < input.length;i++) {
            tree.add(input[i]);
        }
        int i = 0;
        for (Integer num : tree) {
            if (i >= k)
                break;
            list.add(num);
            i++;
        }
        return list;
    }

    public static void main(String[] args) {
        int[] arr = new int[] {4,5,1,6,2,7,3,8,9,10,11,0,16,80};
        ArrayList<Integer> arrayList = GetLeastNumbers_Solution(arr, 9);
        System.out.println(arrayList);
    }
}
